算法设计------Game of Nim

发表于 | 分类于

游戏描述

Nim游戏是对一些放置成堆的一定数量的硬币开始的：硬币和堆的数量取决于你。有两名玩家玩这个游戏，当轮到某位玩家时，他能从某一堆里取任意数量的硬币，但是至少要取一枚硬币，但是也不能从除你取的这个堆以外的其他堆里再取硬币。取得最后一枚硬币的人获胜。

游戏预测

Nim-Sum：对每一堆硬币进行XOR(异或)得到的最终值成为Nim-Sum
例如：设HeapA，HeapB，HeapC，每个堆分别有8，12，13个元素
则Nim-Sum = 8⊕12⊕13 = 9

对于Nim游戏，假设两个玩家足够聪明（都不会犯错），游戏的结果取决于两个因素：

  • 硬币堆数及每堆初始化数量（Nim-Sum值）
  • 游戏从谁开始

如果游戏开始时Nim-Sum非零，首先开始的玩家将获胜，否则首先开始的玩家输掉游戏。

Why?

  • 如果Nim-Sum为零，则无论当前玩家做什么，下一个状态的Nim-Sum都是非0的。
  • 如果Nim-Sum为非零，则当前玩家可以通过计算移除某一堆的硬币数量，使下一状态的Nim-Sum为0
  • 游戏结束时，Nim-Sum为0
  • 更详细的证明

Coding

Nim游戏的结果预测是显而易见的，下面的代码实现了如何完美移动硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// 计算Nim-Sum
int calculateNimSum(int piles[], int n)
{
    int i, nimsum = piles[0];
    for (i=1; i<n; i++)
        nimsum = nimsum ^ piles[i];
    return(nimsum);
}

// 移动硬币
void makeMove(int piles[], int n)
{
    int i, nim_sum = calculateNimSum(piles, n);
 
    // 现在轮到的玩家想要获胜，必须确保移动后的Nim-Sum为0
    if (nim_sum != 0)
    {
        for (i=0; i<n; i++)
        {
            // 如果该移动合法、移动硬币
            if ((piles[i] ^ nim_sum) < piles[i])
            {
            		print("从第%d堆移除%d个硬币\n",i,piles[i]-(piles[i]^nim_sum));
                piles[i] = (piles[i] ^ nim_sum);
                break;
            }
        }
    }
 
    // 在对手不犯错误的情况下，现在轮到的玩家将会失败，这里随机移动硬币即可
    else
    {
        随机移动硬币
    }
    return;
}

如果对你有帮助的话，Star✨下一吧！